Chi tiết

Việc thực hiện một yêu cầu cấp phát bao gồm việc định vị một ô nhớ chưa được sử dụng với kích thước đủ lớn. Yêu cầu này được hoàn thành bằng việc cấp phát một phần từ nguồn chứa lớn của bộ nhớ được gọi là heap(khối xếp) hay free store. Vào bất cứ thời điểm nào, một vài phần của heap đang được sử dụng, còn một vài phần khác thì không do đó có thể được dùng để cấp phát.

Một vài vấn đề có thể làm phức tạp quá trình thực thi, ví dụ như phân mảnh ngoại, xảy ra khi có những khoảng trống nhỏ giữa những ô nhớ đã được cấp phát, điều này sẽ làm những ô nhớ này không khả dụng cho một yêu cầu cấp phát. Siêu dữ liệu của bộ cấp phát cũng có thể thổi phồng kích thước (riêng biệt) của những cấp phát nhỏ. Việc này thường được xử lý bằng quá trình chunking.Hệ thống quản lý bộ nhớ phải theo dõi những cấp phát quá hạn để đảm bảo không xảy ra tràn bộ nhớ.

Hiệu năng

Thuật toán cấp phát bộ nhớ động đặc biệt có ảnh hưởng lớn đến hiệu năng của hệ thống. Một nghiên cứu được Tập đoàn Digital Equipment thực hiện vào năm 1994 đã cho thấy những chi phí vận hành cho một loạt các bộ cấp phát. Độ dài instruction trung bình ngắn nhất để cấp phát một ô nhớ đơn là 52.

Thực hiện

Vì không biết được địa điểm chính xác của việc cấp phát, bộ nhớ được truy cập một cách gián tiếp, thường là thông qua con trỏ tham số. Thuật toán đặc biệt mà được dùng để tổ chức vùng nhớ, cấp phát và giải phóng chunks thì được liên kết với nhân và có thể sử dụng một số phương pháp sau.

Cấp phát ô nhớ kích thước cố định

Cấp phát ô nhớ kích thước cố định, còn được gọi là cấp phát nguồn nhớ, dùng 1 danh sách tự do gồm các ô nhớ có kích thước cố định (thường có cùng kích thước). Cách này hoạt động rất tốt đối với những hệ thống nhúng đơn giản khi không xảy ra việc cấp phát những vật có kích thước quá lớn, nhưng lại thiệt hại vì sự phân mảng, đặc biệt là với những địa chỉ dài. Tuy nhiên do chi phí giảm đáng kể nên phương pháp này có thể tăng cao hiệu suất của một số chương trình thường xuyên cần cấp phát và thu hồi bộ nhớ và thường được sử dụng trong Game

Ô nhớ bạn

Trong hệ thống này, ô nhớ được cấp phát vào nhiếu nguồn nhớ chứ không phải 1, mỗi nguồn nhớ đại diện cho một ô nhớ có kích thước thường là cấp số nhân của 2. Tất cả ô nhớ được giữ trong 1 danh sách liên kết hay cây dữ liệu và các ô nhớ mới được cấp phát được thêm tuần tự vào các nguồn nhớ để sử dụng sau đó. Nếu kích thước yêu cầu quá nhỏ, ô nhớ nhỏ nhất được chọn và chia đôi, một trong 2 mảng chia đôi đó được chọn để tiếp tục cho đến khi nào đạt được kích thước yêu cầu. Khi một ô nhớ được cấp phát, bộ cấp phát sẽ bắt đầu với những ô nhớ lớn vừa đủ để tránh tách ô nhớ không cần thiết. Khi một ô nhớ được giải phóng, nó được so sánh với ô nhớ bạn. Nếu cả hai đều được giải phóng, chúng được gộp lại và đặt trong danh sách ô nhớ lớn kế tiếp